// 图的算法（邻接矩阵和邻接表）
#include "./model/graph.h"
#include "./model/ad-list.h"

// 注：下面注释中，下标为n的点称之为"点n"

/// @brief 获取邻接表的两点之间的距离
/// @param list 邻接表
/// @param start 起点
/// @param end 终点
/// @return 两点距离（权值），不相连返回INFINITE
int getAdListDistance(AdList list, int start, int end)
{
	if (start == end)
	{
		return 0;
	}
	EdgeNode *pointer = list->vertexs[start].firstEdge;
	while (pointer != NULL)
	{
		if (pointer->adjvex == end)
		{
			return pointer->weight;
		}
		pointer = pointer->next;
	}
	return INFINITE;
}

/// @brief 普利姆最小生成树（邻接矩阵）
/// @param graph 传入图
/// @param shortEdgePrior 存放归并的最短边的前驱的数组，长度为顶点个数
/// @param lowcost 存放最短边的长度的数组，长度为顶点个数
void prim(Graph graph, int shortEdgePrior[], int lowcost[])
{
	// shortEdgePrior数组用于存放当前找到的最短边的前驱点下标，比如说shortEdgePrior[1]=3表示点3到点1构成一个最短边，点3为起点，点1为终点
	// lowcost表示存放归并的最短边长度，例如lowcost[1]=10表示到点1的最短边的长度为10
	// 结合上述shortEdgePrior[1]=3与lowcost[1]=10，说明点3到点1构成一个长度为10的最短边
	// 分别表示两个遍历下标、当前找到的最短边的长度以及最短边终点下标（当前待归并点下标）、当前点是否被归并
	int i, j, min, currentFind, included[graph->vertexNum];
	// 初始化
	for (i = 0; i < graph->vertexNum; i++)
	{
		shortEdgePrior[i] = 0;			 // 先开始前驱全部指向起点
		lowcost[i] = graph->edges[0][i]; // 先开始最短边长度为起点到各个点直接距离
		included[i] = 0;
	}
	// 加入自己
	included[0] = 1;
	// 开始寻找最短边，假设有n个顶点，则需要找n - 1趟，因此i表示趟数
	for (i = 1; i < graph->vertexNum; i++)
	{
		min = INFINITE;
		// 开始寻找没有被归并的点，找到其中最短边
		for (j = 0; j < graph->vertexNum; j++)
		{
			if (!included[j] && lowcost[j] < min)
			{
				currentFind = j;
				min = lowcost[j];
			}
		}
		// 这一趟就找到了一个要归并的点，将其加入已归并点集
		included[currentFind] = 1;
		// 更新辅助数组内容，这是一个延展的过程，通过这个刚刚找到的已知点向后寻找，若有比现有最短边更短的边，就将其修改到数组中
		for (j = 0; j < graph->vertexNum; j++)
		{
			if (!included[j] && graph->edges[currentFind][j] < lowcost[j])
			{
				lowcost[j] = graph->edges[currentFind][j];
				shortEdgePrior[j] = currentFind;
			}
		}
	}
}

/// @brief 普利姆最小生成树（邻接表）
/// @param list 邻接表
/// @param shortEdgePrior 存放归并的最短边的前驱的数组，长度为顶点个数
/// @param lowcost 存放最短边的长度的数组，长度为顶点个数
void primAdList(AdList list, int shortEdgePrior[], int lowcost[])
{
	// shortEdgePrior数组用于存放当前找到的最短边的前驱点下标，比如说shortEdgePrior[1]=3表示点3到点1构成一个最短边，点3为起点，点1为终点
	// lowcost表示存放归并的最短边长度，例如lowcost[1]=10表示到点1的最短边的长度为10
	// 结合上述shortEdgePrior[1]=3与lowcost[1]=10，说明点3到点1构成一个长度为10的最短边
	// 分别表示两个遍历下标、当前找到的最短边的长度以及最短边终点下标（当前待归并点下标）、当前点是否被归并、每次待修正距离
	int i, j, min, currentFind, included[list->vertexNum], revise;
	// 初始化
	for (i = 0; i < list->vertexNum; i++)
	{
		shortEdgePrior[i] = 0;						// 先开始前驱全部指向起点
		lowcost[i] = getAdListDistance(list, 0, i); // 先开始最短边长度都是起点到其余各个点的长度
		included[i] = 0;							// 先开始都未被归并
	}
	// 先加入起点自己
	included[0] = 1;
	// 若有n个顶点，归并n - 1趟
	for (i = 1; i < list->vertexNum; i++)
	{
		min = INFINITE;
		// 开始找最短边
		for (j = 0; j < list->vertexNum; j++)
		{
			if (!included[j] && lowcost[j] < min)
			{
				min = lowcost[j];
				currentFind = j;
			}
		}
		// 这样就找到了一个点，其与当前已知点构成的边最短，将其加入已归并点中
		included[currentFind] = 1;
		// 以这个新找到的点为基础，继续向后寻找有没有未知的点和当前点构成更短的边，以修正两个数组
		for (j = 0; j < list->vertexNum; j++)
		{
			revise = getAdListDistance(list, currentFind, j);
			if (!included[j] && revise < lowcost[j])
			{
				shortEdgePrior[j] = currentFind;
				lowcost[j] = revise;
			}
		}
	}
}

/// @brief 根据普利姆最小生成树的结果，还原出一个图对象，并打印结果
/// @param graph 原始图对象
/// @param shortEdgePrior 最短边前驱辅助数组（结果）
/// @param lowcost 最短距离辅助数组
/// @return 最小生成树的图
Graph primResult(Graph graph, int shortEdgePrior[], int lowcost[])
{
	Graph result = createGraph();
	int i;
	// 初始化结果点
	for (i = 0; i < graph->vertexNum; i++)
	{
		insertVex(result, graph->vertexs[i]);
	}
	// 构建结构边，i从1开始是跳过起点
	for (i = 1; i < graph->vertexNum; i++)
	{
		// 双向插入
		insertArc(result, shortEdgePrior[i], i, lowcost[i]);
		insertArc(result, i, shortEdgePrior[i], lowcost[i]);
	}
	// 打印结果，仍然是跳过起点
	printf("归并起点 | 归并终点 | 路径长度\n");
	printf("----------------------------\n");
	for (i = 1; i < graph->vertexNum; i++)
	{
		printf("%-8d | %-8d | %-8d \n", shortEdgePrior[i], i, lowcost[i]);
	}
	return result;
}

/// @brief 求一点到其它所有顶点的最短路径-迪杰斯特拉算法，起点为第一个点（邻接矩阵）
/// @param graph 图对象
/// @param pathArc 存放最短路径的前驱的辅助数组，长度为顶点个数
/// @param shortTable 存放最短路径的长度的辅助数组，长度为顶点个数
void dijkstra(Graph graph, int pathArc[], int shortTable[])
{
	// pathArc数组用于存放起点到达某个点的最短路径的前驱点下标，例如pathArc[1]=2说明最短路径上，到达点1的前驱点是点2（2是1的邻接点）
	// shortTable数组用于存放起点到达某个点的最短路径的长度，例如shortTable[2]=10说明起点到点2的最短路径长度为10
	// included数组用于存放这个点是否已经被包含（被纳入最短路径）
	// 分别表示两个遍历下标、当前找到的最短路径点、当前找到的最短路径值和包含辅助数组
	int i, j, currentFind, min, included[graph->vertexNum];
	// 先初始化
	for (i = 0; i < graph->vertexNum; i++)
	{
		// 起始时起点到其它点最短路径未知，若起点到某点直接可达则前驱设为起点下标，否则前驱用-1表示不可达
		pathArc[i] = graph->edges[0][i] == INFINITE ? -1 : 0;
		// 起始时最短路径就直接初始化为邻接矩阵中，起点到其余所有点的距离
		shortTable[i] = graph->edges[0][i];
		included[i] = 0;
	}
	// 包含起点自己
	included[0] = 1;
	pathArc[0] = 0;
	// 开始寻找最短路径，需要寻找n - 1趟，因此i表示趟数（n为顶点）
	for (i = 1; i < graph->vertexNum; i++)
	{
		min = INFINITE;
		// 找到数组中最短的那个（但是未被包含的）
		for (j = 0; j < graph->vertexNum; j++)
		{
			if (!included[j] && shortTable[j] < min)
			{
				currentFind = j;
				min = shortTable[j];
			}
		}
		// 这一趟下来就找到了起点到某个点的最短路径，将其加入蓝点集（已找到的点）
		included[currentFind] = 1;
		// 进行修正，修正是一个“以曲代直”的过程，如果说起点经过我们刚刚找到的点再到目的点的距离比起点直接到目的点的距离更短，则进行修正
		for (j = 0; j < graph->vertexNum; j++)
		{
			if (!included[j] && shortTable[currentFind] + graph->edges[currentFind][j] < shortTable[j])
			{
				shortTable[j] = shortTable[currentFind] + graph->edges[currentFind][j];
				pathArc[j] = currentFind;
			}
		}
	}
}

/// @brief 求一点到其它所有顶点的最短路径-迪杰斯特拉算法，起点为第一个点（邻接表）
/// @param list 邻接表
/// @param pathArc 存放最短路径的前驱的辅助数组，长度为顶点个数
/// @param shortTable 存放最短路径的长度的辅助数组，长度为顶点个数
void dijkstraAdList(AdList list, int pathArc[], int shortTable[])
{
	// pathArc数组用于存放起点到达某个点的最短路径的前驱点下标，例如pathArc[1]=2说明最短路径上，到达点1的前驱点是点2（2是1的邻接点）
	// shortTable数组用于存放起点到达某个点的最短路径的长度，例如shortTable[2]=10说明起点到点2的最短路径长度为10
	// included数组用于存放这个点是否已经被包含（被纳入最短路径）
	// 分别表示两个遍历下标、当前找到的最短路径点、当前找到的最短路径值和包含辅助数组、用于待修订的距离
	int i, j, currentFind, min, included[list->vertexNum], revise;
	// 初始化
	for (i = 0; i < list->vertexNum; i++)
	{
		// 先开始最短路径表全部为起点到各个点的距离
		shortTable[i] = getAdListDistance(list, 0, i);
		// 起始时起点到其它点最短路径未知，若起点到某点直接可达则前驱设为起点下标，否则前驱用-1表示不可达
		pathArc[i] = shortTable[i] == INFINITE ? -1 : 0;
		// 所有顶点未被加入
		included[i] = 0;
	}
	// 加入起点自己
	included[0] = 1;
	pathArc[0] = 0;
	// 若有n个顶点，则查找n - 1趟
	for (i = 1; i < list->vertexNum; i++)
	{
		min = INFINITE;
		// 先找到路径中最短的
		for (j = 0; j < list->vertexNum; j++)
		{
			if (!included[j] && shortTable[j] < min)
			{
				min = shortTable[j];
				currentFind = j;
			}
		}
		// 这一趟就找到了一个起点到某个点的最短路径，将其加入已知点
		included[currentFind] = 1;
		// 以这个已经找到的最短的路径点为基础，向后继续查找，以曲代直
		for (j = 0; j < list->vertexNum; j++)
		{
			revise = shortTable[currentFind] + getAdListDistance(list, currentFind, j);
			if (!included[j] && revise < shortTable[j])
			{
				pathArc[j] = currentFind;
				shortTable[j] = revise;
			}
		}
	}
}

/// @brief 根据迪杰斯特拉最短路径的结果，输出起点到某个点的最短路径及其长度，并打印整个结果表
/// @param graph 原始图
/// @param pathArc 最短路径前驱辅助数组（结果）
/// @param shortTable 最短路径长度辅助数组（结果）
/// @param end 终点下标
void dijkstraResult(Graph graph, int pathArc[], int shortTable[], int end)
{
	int prior, i;
	// 打印迪杰斯特拉结果表
	printf("迪杰斯特拉结果表：\n");
	printf(" 终点 | 终点前驱 | 路径长度\n");
	printf("-------------------------\n");
	for (i = 0; i < graph->vertexNum; i++)
	{
		printf(" %-4d | %-8d | %-8d\n", i, pathArc[i], shortTable[i]);
	}
	printf("从0到%d的路径：\n", end);
	// 先打印终点
	printf("%d <-", end);
	// 根据前驱数组向前递推路径，直到前驱为起点自己时结束
	for (prior = pathArc[end]; prior != 0; prior = pathArc[prior])
	{
		printf(" %d <-", prior);
	}
	printf(" 0\n");
	printf("路径长度：%d\n", shortTable[end]);
}

/// @brief 求每个点到其它点的最短路径-弗洛伊德算法（邻接矩阵）
/// @param graph 图对象
/// @param pathArc 记录最短路径的前驱的二维数组，长宽都为顶点个数
/// @param shortTable 记录最短路径长度的二维数组，长宽都为顶点个数
void floyd(Graph graph, int **pathArc, int **shortTable)
{
	// pathArc用于记录一点到另一点的最短路径的前驱，例如pathArc[1][2]=3，说明从点1到点2的最短路径要经过点3，这里前驱可能是终点本身，也可能是终点的某邻接点，也可能是最短路径上需要经过的点
	// shortTable用于记录一点到另一点的最短路径的长度，例如shortTable[2][3]=11，说明点2到点3的最短路径长度是11
	int i, j, k;
	// 初始化
	for (i = 0; i < graph->vertexNum; i++)
	{
		for (j = 0; j < graph->vertexNum; j++)
		{
			// 前驱点均初始化为终点本身
			pathArc[i][j] = j;
			// 最短路径长度表初始化为结果矩阵
			shortTable[i][j] = graph->edges[i][j];
		}
	}
	// 开始计算最短路径
	// 同样地，是一个“以曲代直”的过程，假设点i中转经过点k再到点j的距离小于点i直接到点j的距离，则修改路径表，记录该最短路径
	for (i = 0; i < graph->vertexNum; i++)
	{
		for (j = 0; j < graph->vertexNum; j++)
		{
			for (k = 0; k < graph->vertexNum; k++)
			{
				if (shortTable[i][k] + shortTable[k][j] < shortTable[i][j])
				{
					shortTable[i][j] = shortTable[i][k] + shortTable[k][j];
					pathArc[i][j] = pathArc[i][k];
				}
			}
		}
	}
}

/// @brief 求每个点到其它点的最短路径-弗洛伊德算法（邻接表）
/// @param list 邻接表
/// @param pathArc 记录最短路径的前驱的二维数组，长宽都为顶点个数
/// @param shortTable 记录最短路径长度的二维数组，长宽都为顶点个数
void floydAdList(AdList list, int **pathArc, int **shortTable)
{
	// pathArc用于记录一点到另一点的最短路径的前驱，例如pathArc[1][2]=3，说明从点1到点2的最短路径要经过点3，这里前驱可能是终点本身，也可能是终点的某邻接点，也可能是最短路径上需要经过的点
	// shortTable用于记录一点到另一点的最短路径的长度，例如shortTable[2][3]=11，说明点2到点3的最短路径长度是11
	int i, j, k;
	// 初始化
	for (i = 0; i < list->vertexNum; i++)
	{
		for (j = 0; j < list->vertexNum; j++)
		{
			pathArc[i][j] = j;								  // 先开始前驱全部为终点本身
			shortTable[i][j] = getAdListDistance(list, i, j); // 先开始最短路径即为每个点到每个点的距离
		}
	}
	// 开始寻找
	for (i = 0; i < list->vertexNum; i++)
	{
		for (j = 0; j < list->vertexNum; j++)
		{
			for (k = 0; k < list->vertexNum; k++)
			{
				// 如果从i到k再到j，比起直接从i到j短，则修正
				if (shortTable[i][k] + shortTable[k][j] < shortTable[i][j])
				{
					shortTable[i][j] = shortTable[i][k] + shortTable[k][j];
					pathArc[i][j] = pathArc[i][k];
				}
			}
		}
	}
}

/// @brief 根据弗洛伊德算法结果，打印结果表，并输出某一条最短路径
/// @param graph 原始图
/// @param pathArc 最短路径前驱数组（结果）
/// @param shortTable 最短路径长度数组（结果）
/// @param start 要输出最短路径的起点下标
/// @param end 要输出的最短路径的终点下标
void floydResult(Graph graph, int **pathArc, int **shortTable, int start, int end)
{
	int i, j, k;
	printf("弗洛伊德算法结果表：\n");
	printf("最短路径前驱：\n");
	for (i = 0; i < graph->vertexNum; i++)
	{
		for (j = 0; j < graph->vertexNum; j++)
		{
			printf("%-2d ", pathArc[i][j]);
		}
		printf("\n");
	}
	printf("最短路径长度：\n");
	for (i = 0; i < graph->vertexNum; i++)
	{
		for (j = 0; j < graph->vertexNum; j++)
		{
			printf("%-3d ", shortTable[i][j]);
		}
		printf("\n");
	}
	printf("%d到%d的最短路径：\n", start, end);
	// 先打印起点
	printf("%d ->", start);
	// 开始递推：
	// 比如说pathArc[0][8]=1，说明点0到点8的路径上要经过点1，然后找到pathArc[1][8]=2，说明要经过点2，然后找到pathArc[2][8]=4，说明要经过点4...
	// 这样，易推出路径为start -> 1 -> 2 -> 4 -> ... -> 8
	// k表示当前找到的路径点
	for (k = pathArc[start][end]; k != end; k = pathArc[k][end])
	{
		printf(" %d ->", k);
	}
	// 打印终点
	printf(" %d\n", end);
	printf("其长度为：%d\n", shortTable[start][end]);
}

int main()
{
	// 初始化测试数据
	Graph graph = createGraph();
	for (char c = '1'; c <= '7'; c++)
	{
		insertVex(graph, c);
	}
	int start[] = {0, 0, 1, 4, 1, 3, 4, 2, 5, 0};
	int end[] = {1, 4, 3, 3, 2, 5, 6, 5, 6, 3};
	int weight[] = {3, 5, 7, 10, 2, 9, 1, 11, 3, 20};
	insertArcs(graph, start, end, weight, sizeof(start) / sizeof(int), 1);
	printGraph(graph);
	// 最小生成树
	int lowcost[graph->vertexNum], shortEdgePrior[graph->vertexNum];
	prim(graph, shortEdgePrior, lowcost);
	Graph r = primResult(graph, shortEdgePrior, lowcost);
	printGraph(r);
	// 迪杰斯特拉
	int pathArc[graph->vertexNum], shortTable[graph->vertexNum];
	dijkstra(graph, pathArc, shortTable);
	dijkstraResult(graph, pathArc, shortTable, 6);
	// 弗洛伊德算法
	int **pathArc2 = (int **)calloc(graph->vertexNum, sizeof(int *)), **shortTable2 = (int **)calloc(graph->vertexNum, sizeof(int *)), i;
	for (i = 0; i < graph->vertexNum; i++)
	{
		pathArc2[i] = (int *)calloc(graph->vertexNum, sizeof(int));
		shortTable2[i] = (int *)calloc(graph->vertexNum, sizeof(int));
	}
	floyd(graph, pathArc2, shortTable2);
	floydResult(graph, pathArc2, shortTable2, 0, 6);
	printf("----------------------------------------------------------------\n");
	AdList list = createAdList();
	for (char c = '1'; c <= '7'; c++)
	{
		adListInsertVex(list, c);
	}
	int n = sizeof(start) / sizeof(int);
	for (i = 0; i < n; i++)
	{
		adListInsertArc(list, start[i], end[i], weight[i]);
		adListInsertArc(list, end[i], start[i], weight[i]);
	}
	printAdList(list);
	// 最小生成树
	primAdList(list, shortEdgePrior, lowcost);
	primResult(graph, shortEdgePrior, lowcost);
	// 迪杰斯特拉
	dijkstraAdList(list, pathArc, shortTable);
	dijkstraResult(graph, pathArc, shortTable, 6);
	// 弗洛伊德算法
	floydAdList(list, pathArc2, shortTable2);
	floydResult(graph, pathArc2, shortTable2, 0, 6);
	return 0;
}